package algorithms.leaning.class25;

import common.util.MyUtil;

import java.util.ArrayDeque;
import java.util.Deque;

/**
 * 给定一个非负数组nums，代表直方图
 * 返回直方图的最大长方形面积
 *
 * @author guichang
 * @date 2021/6/27
 */

@SuppressWarnings("all")
public class Code3_单调栈_直方图最大面积 {

    public static void main(String[] args) {
        int[] nums = MyUtil.createArray(3, 5, 4, 4, 15, 20);
        MyUtil.print(maxArea(nums));
    }

    /**
     * 以nums[i]做高往左右两边扩的最大面积
     */
    public static int maxArea(int[] nums) {
        if (nums == null || nums.length == 0) {
            return 0;
        }
        int N = nums.length;
        int ans = 0;
        Deque<Integer> stack = new ArrayDeque<>();
        for (int i = 0; i < N; i++) {
            while (!stack.isEmpty() && nums[i] <= nums[stack.peek()]) {
                Integer top = stack.pop(); // 当前计算的坐标
                int left = stack.isEmpty() ? 0 : stack.peek() + 1; // 最左边能到的位置
                int right = i - 1;// 最右能到的位置
                ans = Math.max(ans, nums[top] * (right - left + 1)); // 面积比较
            }
            stack.push(i);
        }
        while (!stack.isEmpty()) {
            Integer top = stack.pop();
            int left = stack.isEmpty() ? 0 : stack.peek() + 1; // 最左边能到的位置
            int right = N - 1; // 最右能到的位置
            ans = Math.max(ans, nums[top] * (right - left + 1)); // 面积比较
        }
        return ans;
    }

}